import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.CsvSource;

/**
 * 实现 strStr() 函数
 * 题目：给定一个haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1
 * <p>
 * 示例 1:
 * 输入: haystack = "hello", needle = "ll"
 * 输出: 2
 * 示例 2:
 * <p>
 * 输入: haystack = "aaaaa", needle = "bba"
 * 输出: -1
 * 说明: 当needle是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
 * <p>
 * 对于本题而言，当needle是空字符串时我们应当返回 0 。这与C语言的strstr()以及 Java的indexOf()定义相符。
 * <p>
 * 来源：力扣（LeetCode-28）
 * 链接：https://leetcode-cn.com/problems/implement-strstr
 *
 * @author godfrey
 * @since 2020-10-13
 */
@DisplayName("实现 strStr()-返回字符串中第一次出现的needle的指针")
public class ImplementStrstr extends BaseTest {

    @DisplayName("暴力解法-时间复杂度O(N*M)，空间复杂度O(1)")
    @ParameterizedTest
    @CsvSource({"ABCEDBCDACDEFCDS,CDS", "ACDBCDA,CD", "ACDBCDA,''", "'',a", "ACDBCDA,DDD", "'',''"})
    void strStr(final String haystack, final String needle) {
        final int n = haystack.length(), m = needle.length();
        if (m == 0) {
            System.out.println(0);
            return;
        }
        final int times = n - m + 1;
        if (times <= 0) {
            System.out.println(-1);
            return;
        }
        for (int i = 0; i < times; ++i) {
            int j = i, k = 0;
            while (j < n && k < m && haystack.charAt(j) == needle.charAt(k)) {
                ++j;
                ++k;
            }
            if (k == m) {
                System.out.println(i);
                return;
            } else if (j == times - 1) {
                System.out.println(-1);
            }
        }
    }

    @DisplayName("子串逐一比较-时间复杂度：O((N - L)L),空间复杂度为O(1)")
    @ParameterizedTest
    @CsvSource({"ABCEDBCDACDEFCDS,CDS", "ACDBCDA,CD", "ACDBCDA,''", "'',a", "ACDBCDA,DDD", "'',''"})
    void strStr2(final String haystack, final String needle) {
        final int n = haystack.length(), L = needle.length();
        final int end = n - L + 1;
        for (int index = 0; index < end; index++) {
            if (haystack.substring(index, index + L).equals(needle)) {
                System.out.println(index);
                return;
            }
        }
        System.out.println(-1);
    }

    @DisplayName("双指针法-时间复杂度：O((N - L)L),最优的时候为O(N),空间复杂度：O(1)")
    @ParameterizedTest
    @CsvSource({"ABCEDBCDACDEFCDS,CDS", "ACDBCDA,CD", "ACDBCDA,''", "'',a", "ACDBCDA,DDD", "'',''"})
    void strStr3(final String haystack, final String needle) {
        final int L = needle.length(), n = haystack.length();
        if (L == 0) {
            System.out.println(0);
            return;
        }
        int pn = 0;
        while (pn < n - L + 1) {
            //找到的一个字符与首字符一致的位置
            while (pn < n - L + 1 && haystack.charAt(pn) != needle.charAt(0)) {
                ++pn;
            }
            //逐个比较
            int currLen = 0, pL = 0;
            while (pL < L && pn < n && haystack.charAt(pn) == needle.charAt(pL)) {
                ++pn;
                ++pL;
                ++currLen;
            }

            //匹配完
            if (currLen == L) {
                System.out.println(pn - L);
                return;
            }
            //回退指针
            pn = pn - currLen + 1;
        }
        System.out.println(-1);
    }

    @DisplayName("调用库函数")
    @ParameterizedTest
    @CsvSource({"ABCEDBCDACDEFCDS,CDS", "ACDBCDA,CD", "ACDBCDA,''", "'',a", "ACDBCDA,DDD", "'',''"})
    void strStr4(final String haystack, final String needle) {
        System.out.println(haystack.indexOf(needle));
    }

    @DisplayName("KMP-时间复杂度O(N+M)，空间复杂度O(M)")
    @ParameterizedTest
    @CsvSource({"ABCEDBCDACDEFCDS,CDS", "ACDBCDA,CD", "ACDBCDA,''", "'',a", "ACDBCDA,DDD", "'',''"})
    void strStr5(final String haystack, final String needle) {
        final int n = haystack.length(), m = needle.length();
        if (n == 0 && m == 0) {
            System.out.println(0);
            return;
        }
        if (m == 0) {
            System.out.println(0);
            return;
        }
        int[] next = new int[m];
        computePrefix(needle, next);
        for (int i = 0, j = -1; i < n; ++i) {
            while (j > -1 && needle.charAt(j + 1) != haystack.charAt(i)) {
                j = next[j];
            }
            if (haystack.charAt(i) == needle.charAt(j + 1)) {
                ++j;
            }
            if (j == m - 1) {
                System.out.println(i - j);
                return;
            }
        }
        System.out.println(-1);
    }

    /**
     * 计算部分匹配表，即next数组
     *
     * @param needle 模式串
     * @param next   next数组
     */
    private static void computePrefix(final String needle, final int[] next) {
        int j = -1;
        next[0] = j;
        for (int i = 1; i < needle.length(); ++i) {
            while (j > -1 && needle.charAt(j + 1) != needle.charAt(i)) {
                j = next[j];
            }
            if (needle.charAt(i) == needle.charAt(j + 1)) {
                ++j;
            }
            next[i] = j;
        }
    }

    @DisplayName("Rabin Karp(滚动哈希)-时间复杂度：O(N),空间复杂度：O(1)O(1)")
    @ParameterizedTest
    @CsvSource({"ABCEDBCDACDEFCDS,CDS", "ACDBCDA,CD", "ACDBCDA,''", "'',a", "ACDBCDA,DDD", "'',''"})
    void strStr6(final String haystack, final String needle) {
        final int L = needle.length(), n = haystack.length();
        if (n < L) {
            System.out.println(-1);
            return;
        }
        int a = 26;
        //防止溢出
        long modules = (long) Math.pow(2, 31);
        long hayHash = 0, needleHash = 0;
        //计算haystack和needle滚动hash
        for (int i = 0; i < L; ++i) {
            hayHash = (hayHash * a + charToInt(i, haystack)) % modules;
            needleHash = (needleHash * a + charToInt(i, needle)) % modules;
        }
        //滚动hash值相等，可能第一个就匹配，也needle是空串
        if (hayHash == needleHash) {
            System.out.println(0);
            return;
        }
        long aL = 1;
        for (int i = 0; i < L; ++i) {
            aL = (aL * a) % modules;
        }
        final int times = n - L + 1;
        for (int start = 1; start < times; start++) {
            hayHash = (hayHash * a - charToInt(start - 1, haystack) * aL
                    + charToInt(start + L - 1, haystack)) % modules;
            if (hayHash == needleHash) {
                System.out.println(start);
                return;
            }
        }
        System.out.println(-1);
    }

    private int charToInt(int idx, String s) {
        return (int) s.charAt(idx) - (int) 'a';
    }

}
